package deepbrain.iit;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

/**
 * current version: 1.1
 * 
 * history: 
 *   -version 1.0 
 *       implement partitioning N nodes into K group, print the
 *       result out, result not saved.  --Mar24,2009 
 *   -version 1.1
 *       some comments added in. --Mar25,2009
 * 
 * This algorithm is attributed to Virgil Griffiths http://virgil.gr
 * 
 * @author Qiao Yan
 * @create 2009-3-23
 */
public class PartitionGenerator implements Iterable<Partition<Integer>> {

	private List<Partition<Integer>> partitions;

	public PartitionGenerator(int numOfNodes, int maxNumOfParts) {
		partitions = generatePartitions(numOfNodes, maxNumOfParts);
	}

	public static List<Partition<Integer>> generatePartitions(int numOfNodes,
			int maxNumOfParts) {
		ArrayList<Integer> cue = new ArrayList<Integer>();
		Partition<Integer> res = new Partition<Integer>();
		for (int i = 0; i < numOfNodes; i++)
			cue.add(i);
		List<Partition<Integer>> result = new ArrayList<Partition<Integer>>();
		make_compartments(maxNumOfParts, res, cue, result);
		return result;
	}

	@SuppressWarnings("unchecked")
	private static Partition<Integer> add_entry(Partition<Integer> input,
			int c, int w) {
		if (c >= input.numOfParts()) {
			ArrayList<Integer> leer = new ArrayList<Integer>();
			input.addPart(leer);
		}

		ArrayList<Integer> clone = (ArrayList<Integer>) input.part(c).clone(); // generate
		/**
		 * a copy of input[c], so that the input won't be modified
		 */
		clone.add(w);
		input.setPart(c, clone);
		return input;
	}

	// this function generates recursively the bell number partition
	@SuppressWarnings("unchecked")
	private static void make_compartments(int maxNumOfParts,
			Partition<Integer> res, ArrayList<Integer> cue,
			List<Partition<Integer>> result) {
		// Only continue if we have <= MAX_NUM_PARTS. (aka: if have more
		// than
		// MAX_NUM_PARTS, stop recursing)
		if (res.numOfParts() <= maxNumOfParts) {
			if (cue.size() == 0) {
				result.add(res);

			} else {
				// sub partition not complete
				int j = cue.get(0);
				cue.remove(0);

				for (int i = 0; i < res.numOfParts() + 1; i++) {
					make_compartments(maxNumOfParts, add_entry(res.clone(), i,
							j), (ArrayList<Integer>) (cue.clone()), result); // use
					/**
					 * clone in order to keep List res & cue from being changed
					 */
				}
			}
		}
	}

	public Iterator<Partition<Integer>> iterator() {
		return partitions.iterator();
	}

	public static void main(String[] args) {
		long startTime = System.currentTimeMillis();
		for (Partition<Integer> partition : new PartitionGenerator(12, 2)) {
			System.out.println(partition);
		}
		System.out.println(System.currentTimeMillis() - startTime);
	}

}
